package dataStructure;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 哈夫曼树研究测试
 * 
 * @author Bankarian
 *
 */
public class Huffman {
	/** 哈夫曼节点类 */
	public static class Node implements Comparable<Node> {
		Node fath;
		Node left, right;
		String key;
		int value;
		Queue<Node> pq = new PriorityQueue<>();

		public Node(Node f, Node l, Node r) {
			this.fath = f;
			this.left = l;
			this.right = r;
		}

		public Node(Node l, Node r) {
			this.left = l;
			this.right = r;
		}

		public Node(int value, String key) {
			this.value = value;
			this.key = key;
		}

		public int compareTo(Node o) {
			return this.value - o.value;
		}
	}

	public Huffman(List<Node> nodeList) {
		pq = new PriorityQueue<Huffman.Node>();
		for (Node n : nodeList) {
			pq.add(n);
		}
		createHuffman();
	}

	public Node getRoot() {
		return this.root;
	}

	public static void displayTree(Node root) {
		if (root == null)
			return;
		else
			System.out.print(root.value + " ");
		displayTree(root.left);
		displayTree(root.right);
	}

	public static void displayCode(Node root, String code) {
		if (root == null)
			return;
		else if (root.key != null)
			System.out.println(root.key + ", value:" + root.value + ", huffman code:" + code);
		displayCode(root.left, code + "0");
		displayCode(root.right, code + "1");
	}

	private Node root = null;
	private Queue<Node> pq = null;

	private void createHuffman() {
		while (pq.size() > 1) {
			Node n1 = pq.poll();
			Node n2 = pq.poll();
			Node nextNode = new Node(n1, n2);
			nextNode.value = n1.value + n2.value;
			n1.fath = nextNode;
			n2.fath = nextNode;
			pq.add(nextNode);
		}
		if (pq.size() == 1)
			root = pq.poll();
	}

}
